home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Text⁄Files / Grep src / GrepPattern.c < prev   
Encoding:
C/C++ Source or Header  |  1986-10-30  |  10.0 KB  |  532 lines  |  [TEXT/KAHL]
  1. /*
  2.     GrepCompile - routines for compiling patterns into internal form,
  3.     and for matching strings against the compiled pattern.
  4. */
  5.  
  6.  
  7. # include    <DialogMgr.h>
  8. # include    "Grep.h"
  9.  
  10. /*  special internal chars for compiled pattern  */
  11.  
  12. # define    CCL        1        /* match characters in class */
  13. # define    NCCL    2        /* all but characters in class */
  14. # define    CRANGE    3        /* range of chars */
  15. # define    ENDCCL    4        /* end char class */
  16. # define    ANY        5        /* match any char */
  17. # define    CLOSURE    6        /* closure */
  18. # define    EOL        7        /* end of line */
  19.  
  20.  
  21. /*  pattern compilation and matching vars  */
  22.  
  23. static Boolean    matchBol;            /* match beginning of line? */
  24. static int        pix;                /* index into pattern */
  25. static int        pMark;
  26. static Boolean    canClose;
  27.  
  28. /*
  29.     Pattern buffers.  rawPattern is the text typed by user into
  30.     the dialog box.  cmpPattern is the compiled pattern.  Initially
  31.     they are both empty.  (Format of the nil compiled pattern is
  32.     dependent on algorithm used to compile rawPattern.)  This is
  33.     legal - it matches every line.  If a file is grepped without
  34.     specifying a pattern, therefore, the whole file will be
  35.     displayed.  A side effect of this is to turn grep on WORD files
  36.     into a WORD-to-TEXT file converter when the save output option
  37.     is turned on.
  38. */
  39.  
  40. char        rawPattern[bufSiz] = "";
  41. static char    cmpPattern[bufSiz] = "";
  42.  
  43.  
  44. /* ----------------------------------------------------------------------- */
  45. /*                        pattern-compilation routines                     */
  46. /* ----------------------------------------------------------------------- */
  47.  
  48.  
  49.  
  50. /*
  51.     Add char to pattern (may be a metachar, not necessarily
  52.     a literal character to match)
  53. */
  54.  
  55. AddPatChar (c)
  56. char    c;
  57. {
  58.     if (ignoreCase && c >= 'A' && c <= 'Z')
  59.         c += 'a' - 'A';
  60.     cmpPattern[pix] = c;
  61.     ++pix;
  62.     cmpPattern[pix] = 0;
  63.  
  64. }    /* AddPatChar */
  65.  
  66.  
  67. /*
  68.     Put a closure indicator into the pattern, in front of the
  69.     stuff that's to be closed.
  70. */
  71.  
  72. AddClosure ()
  73. {
  74. register int    i;
  75.  
  76.     ++pix;
  77.     for (i = pix; i > pMark; --i)
  78.     /*loop (, i = pix,    , --i <= pMark)*/
  79.         cmpPattern [i] = cmpPattern [i-1];
  80.     cmpPattern [pMark] = CLOSURE;
  81.     canClose = false;
  82.  
  83. }    /* AddClosure */
  84.  
  85.  
  86. /*
  87.     have found something that may be followed by a closure.  set
  88.     canClose to indicate that fact, and set a mark to remember where
  89.     the closable thing is.
  90. */
  91.  
  92. MarkIt ()
  93. {
  94.     pMark = pix;        /* set mark in case closure comes up next */
  95.     canClose = true;
  96. }
  97.  
  98.  
  99. /*
  100.     Get escaped char (char following '\').  The only special one
  101.     right now is '\t', which is turned into a tab.  Caller must check
  102.     that return value isn't zero.
  103. */
  104.  
  105. char EscapeChar (c)
  106. char    c;
  107. {
  108.     return (c == 't' ? '\t' : c);
  109. }
  110.  
  111. /*
  112.     compile character class.  pass pointer to char after '[' that begins
  113.     the class pattern.  Return nil if (error, else pointer to char
  114.     after closing ']' bracket.
  115. */
  116.  
  117. StringPtr Class (p)
  118. register StringPtr    p;
  119. {
  120. register char    c, type, low, high;
  121.  
  122.     type = CCL;            /* 'character class' metachar */
  123.     if (*p == '^')
  124.     {
  125.         type = NCCL;        /* 'match all but this class' metachar */
  126.         ++p;
  127.     }
  128.     AddPatChar (type);
  129.     for (;;)
  130.     {
  131.         c = *p;
  132.         ++p;
  133.         if (c == '\\')
  134.         {
  135.             c = EscapeChar (*p);
  136.             ++p;
  137.         }
  138.         else if (c == ']')
  139.             break;                /* end of class pattern */
  140.         if (c == 0)
  141.             return (nil);        /* missing ']' - pattern error */
  142.         if (*p != '-')
  143.             AddPatChar (c);
  144.         else        /* range */
  145.         {
  146.             low = c;                    /* low end */
  147.             ++p;
  148.             high = *p;                    /* high end */
  149.             ++p;
  150.             if (high == 0)
  151.                 return (nil);            /* pattern error */
  152.             AddPatChar (CRANGE);
  153.             AddPatChar (low);
  154.             AddPatChar (high);
  155.         }
  156.     }
  157.     AddPatChar (ENDCCL);
  158.     return (p);                            /* all ok */
  159.  
  160. }    /* class */
  161.  
  162.  
  163. /*
  164.     COMPILE - compile string into internal form suitable for efficient
  165.         pattern matching.  String should be in C format.
  166. */
  167.  
  168. Boolean Compile (p)
  169. register StringPtr    p;
  170. {
  171. register char    c;
  172.  
  173.     pix = 0;
  174.     cmpPattern[0] = 0;
  175.     canClose = false;
  176.     matchBol = false;
  177. /*
  178.     check for ^ - it's only special at beginning of line
  179. */
  180.     if (*p == '^')
  181.     {
  182.         matchBol = true;
  183.         ++p;
  184.     }
  185.     for (;;)
  186.     {
  187.         c = *p;
  188.         ++p;
  189.  
  190.         if (c == '*')
  191.         {
  192. /*
  193.     if (canClose is true, there was a preceding pattern which can be
  194.     closed (not closure, ^ or $), so close it.  otherwise, take *
  195.     literally.
  196. */
  197.             if (canClose)    /* something to close */
  198.             {
  199.                 AddClosure ();
  200.                 continue;
  201.             }
  202.         }
  203.  
  204. /*
  205.     $ only special at end of line
  206. */
  207.         if (c == '$' && *p == 0)
  208.         {
  209.             AddPatChar ((char) EOL);
  210.             continue;
  211.         }
  212. /*
  213.     at this point we know we have a character that can be followed by a
  214.     closure, so mark the pattern position.
  215. */                
  216.         MarkIt ();
  217.  
  218. /*
  219.     use most escaped chars literally, except null, which is an error,
  220.     and \t, which is a tab.
  221. */
  222.         if (c == '\\')
  223.         {
  224.             c = EscapeChar (*p++);
  225.             if (c == 0)
  226.                 return (false);                    /* pattern error */
  227.             AddPatChar (c);
  228.             continue;
  229.         }
  230.         if (c == 0) break;                        /* done compiling */
  231.         switch (c)
  232.         {
  233.             case '.': AddPatChar (ANY); break;    /* match any char */
  234.             case '[':                            /* match character class */
  235.             {
  236.                 if ((p = Class (p)) == nil)
  237.                     return (false);                /* class pattern error */
  238.                 break;
  239.             }
  240.             default: AddPatChar (c);            /* match char literally */
  241.         }
  242.  
  243.     }    /* loop */
  244.  
  245.     return (true);                                /* all ok */
  246.  
  247. }    /* compile */
  248.  
  249.  
  250. /* ----------------------------------------------------------------------- */
  251. /*                         pattern-matching routines                       */
  252. /* ----------------------------------------------------------------------- */
  253.  
  254. /*
  255.     NEXTPOS - find position in pattern of next component to match
  256. */
  257.  
  258. StringPtr NextPos (p)
  259. register StringPtr    p;
  260. {
  261. register char    c;
  262.  
  263.     c = *p;
  264.     ++p;
  265.     if (c == CCL || c == NCCL)
  266.     {
  267.         do        /* look for end of class stuff */
  268.         {
  269.             c = *p;
  270.             ++p;
  271.         } while (c != ENDCCL);
  272.     }
  273.     return (p);
  274.  
  275. }    /* NextPos */
  276.  
  277.  
  278. Boolean InClass (c, p)
  279. register char        c;
  280. register StringPtr    p;
  281. {
  282. register char    high, low, pc;
  283.  
  284.     for (;;)
  285.     {
  286.         pc = *p;
  287.         ++p;
  288.         if (pc == ENDCCL)
  289.             return (false);
  290.         if (pc == CRANGE)        /* range */
  291.         {
  292.             low = *p;
  293.             ++p;
  294.             high = *p;
  295.             ++p;
  296.             if (low <= c && c <= high)
  297.                 break;            /* it's within the range */
  298.         }
  299.         else if (c == pc)
  300.             break;                /* it matched this char of class */
  301.     }
  302.     return (true);
  303.  
  304. }    /* InClass */
  305.  
  306. /*
  307.     OMATCH - match character c against the current pattern position.
  308. */
  309.  
  310. Boolean omatch (c, p)
  311. register char        c;
  312. register StringPtr    p;
  313. {
  314. register char    pc;
  315.  
  316.     if (ignoreCase && c >= 'A' && c <= 'Z')
  317.         c += 'a' - 'A';
  318.     pc = *p;
  319.     ++p;
  320.     switch (pc)
  321.     {
  322.         case CCL: return (InClass (c, p));
  323.         case NCCL: return (!InClass (c, p));
  324.         case ANY: return (c != 0);    /* don't match end of line */
  325.         default: return (c == pc);
  326.     }
  327.  
  328. }    /* omatch */
  329.  
  330.  
  331. /*
  332.     try to match pattern p at the given position in string s
  333. */
  334.  
  335. Boolean amatch (s, p)
  336. register StringPtr    s, p;
  337. {
  338. register StringPtr    cursp;
  339.  
  340.     if (*p == 0)
  341.         return (true);        /* end of pattern, have matched it */
  342.     if (*p == EOL)
  343.         return (*s == 0);    /* must be end of string to match EOL */
  344.  
  345.     if (*p == CLOSURE)
  346.     {
  347.  
  348. /*
  349.     advance as far as possible, matching the current pattern position.
  350.     when omatch fails, s will point 1 past the character that failed.
  351.     then back up one and try to match rest of pattern.  if that fails,
  352.     keep retreating until back at point of original closure start
  353. */
  354.  
  355.         ++p;        /* skip closure marker */
  356.         cursp = s;    /* save current string position */
  357.  
  358.         while (omatch (*s++, p))
  359.             /* march! */ ;
  360.  
  361.         do                        /* keep backing up */
  362.         {
  363.             --s;
  364.             if (amatch (s, NextPos (p)))
  365.                 return (true);
  366.         } while (s > cursp);
  367.         return (false);
  368.     }
  369.  
  370.     if (omatch (*s++, p))
  371.         return (amatch (s, NextPos (p)));
  372.     return (false);
  373.  
  374. }    /* amatch */
  375.  
  376.  
  377. /*
  378.     MATCH - match string s against the compiled pattern
  379.  
  380.     if matchBol is true, then anchor the match to the beginning of the
  381.     string, else try the pattern against successive string positions until
  382.     the match succeeds or the end of the string is reached.
  383.  
  384.     s should be in C format.
  385. */
  386.  
  387. Boolean match (s)
  388. register StringPtr    s;
  389. {
  390.     if (matchBol)    /* anchored match */
  391.     {
  392.         return (amatch (s, cmpPattern));
  393.     }
  394.     for (;;)            /* floating match */
  395.     {
  396.         if (amatch (s, cmpPattern))
  397.             return (true);
  398.         if (*s == 0)
  399.             return (false);    /* end of string but no match */
  400.         ++s;
  401.     }
  402.  
  403. }    /* match */
  404.  
  405.  
  406. /*
  407.     Routines for presenting the pattern entry dialog.
  408. */
  409.  
  410.  
  411. /*
  412.     pattern dialog items
  413.  
  414.     item    type
  415.     1        ok button
  416.     2        cancel button
  417.     3        prompt
  418.     4        edittext item for typing in pattern
  419.     5        "lines not containing pattern" radio button
  420.     6        "print line numbers" check box
  421.     7        "ignore case" check box
  422.  
  423.     Puts the string entered into theString, which on return is
  424.     empty if either the user clicked Cancel or typed no string
  425.     and clicked ok.
  426. */
  427.  
  428. enum
  429. {
  430.     okButton = 1,
  431.     cancelButton,
  432.     promptStatText,
  433.     patText,
  434.     lineOption,
  435.     numberOption,
  436.     caseOption
  437. };
  438.  
  439.  
  440. static DialogPtr    theDialog;
  441.  
  442.  
  443.  
  444. /*
  445.     Set or get the value of a checkbox (i.e., boolean) dialog item
  446. */
  447.  
  448. SetDBoolean (itemNo, itemValue)
  449. int        itemNo;
  450. Boolean    itemValue;
  451. {
  452. Handle    itemHandle;
  453. int        itemType;
  454. Rect    r;
  455.  
  456.     GetDItem (theDialog, itemNo, &itemType, &itemHandle, &r);
  457. /*
  458.     Note type conversion here.  True turns the control on.
  459. */
  460.     SetCtlValue (itemHandle, (int) itemValue);
  461. }
  462.  
  463.  
  464. Boolean GetDBoolean (itemNo)
  465. int        itemNo;
  466. {
  467. Handle    itemHandle;
  468. int        itemType;
  469. Rect    r;
  470.  
  471.     GetDItem (theDialog, itemNo, &itemType, &itemHandle, &r);
  472.     return ((Boolean) GetCtlValue (itemHandle));
  473. }
  474.  
  475.  
  476. Boolean GetPatDlog ()
  477. {
  478. int        itemNo, itemType;
  479. Handle    itemHandle;
  480. Rect    r;
  481. register Boolean    result;
  482.  
  483.     theDialog = GetNewDialog (resBase + patBox, nil, -1L);
  484.     SetDBoolean (lineOption, !prtMatches);
  485.     SetDBoolean (numberOption, prtLineNum);
  486.     SetDBoolean (caseOption, ignoreCase);
  487.     GetDItem (theDialog, patText, &itemType, &itemHandle, &r);
  488.     SetIText (itemHandle, rawPattern);
  489.     SelIText (theDialog, patText, 0, 32760);
  490.     ShowWindow (theDialog);
  491.     for (;;)
  492.     {
  493.         ModalDialog (nil, &itemNo);
  494.         if (itemNo == cancelButton)
  495.         {
  496.             result = false;
  497.             break;
  498.         }
  499.         else if (itemNo == okButton)
  500.         {
  501.             GetDItem (theDialog, patText, &itemType, &itemHandle, &r);
  502.             GetIText (itemHandle, rawPattern);
  503.             prtMatches = !GetDBoolean (lineOption);
  504.             prtLineNum = GetDBoolean (numberOption);
  505.             ignoreCase = GetDBoolean (caseOption);
  506.             result = true;
  507.             break;
  508.         }
  509.         else        /* must be option check box - flip value */
  510.         {
  511.             SetDBoolean (itemNo, !GetDBoolean (itemNo));
  512.         }
  513.     }
  514.  
  515.     DisposDialog (theDialog);
  516.     return (result);
  517.  
  518. }    /* GetPatDlog */
  519.  
  520.  
  521. GetGrepPat ()
  522. {
  523.     if (GetPatDlog ())
  524.     {
  525.         PtoCstr (rawPattern);
  526.         havePat = Compile (rawPattern);
  527.         CtoPstr (rawPattern);
  528.         if (!havePat)
  529.             Alarm ("\pBad Pattern");
  530.     }
  531. }
  532.